The present invention relates to system behavior measurement and correlation in general, and applications therefor.
The practical application of behavior correlation techniques is well known in many fields of science and engineering. For example, correlations between levels of automobile traffic and traffic accidents often serve as both a starting point and a benchmark in road safety programs, while correlations between advertising expenditure over the course of an advertising campaign and consumer purchases are invaluable in determining return on investment and providing other measures of effectiveness.
Whether behavior correlation techniques may be used to determine the presence of mutual interaction between two elements of a system should be examined. Some systems, such as computer networks, have elements that mutually interact, such as by communicating with each other. Computer networks, for example, typically have many network devices that are physically and logically interconnected via communication links. While information about the devices, such as their network address, is typically readily available, information regarding how the devices are physically interconnected must typically be derived manually or by employing automatic topology discovery techniques. Thus, were behavior correlation techniques successfully applied to determine the presence of mutual interaction between elements of a computer network, such techniques could be used to determine how network devices are interconnected. Unfortunately, some systems, including computer networks, have mutually interacting elements whose behavior functions diverge over time with respect to one another, thus making behavior correlation difficult.
The present invention provides a method for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements.
In one aspect of the present invention there is provided a method for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements, the method including measuring the behavior of two elements of a system over time with respect to mutual interaction, thereby producing two behavior functions, expressing a plurality of constraints on a theoretical distance c between the behavior functions, and determining that the elements are behaving as mutually interacting elements where there exists an actual distance c satisfies the constraints.
In another aspect of the present invention the expressing step comprises maintaining an upper bound and a lower bound on the theoretical distance c, and the determining step comprises determining where the lower bound is smaller than or equal to the higher bound for any of the constraints.
In another aspect of the present invention the expressing step comprises expressing each of the constraints using at least two time-consecutive samples (an, an+1) of one of the functions and at least one sample (bn) of the other of the functions that is time-intermediate the time-consecutive samples.
In another aspect of the present invention the expressing step comprises expressing each of the constraints as (anxe2x88x92bn)xe2x89xa6cxe2x89xa6(an+1xe2x88x92bn).
In another aspect of the present invention the expressing step comprises expressing each of the distances using at least two time-consecutive samples (an, an+1) of one of the functions and at least one sample (bn) of the other of the functions that is taken at the same time as one of the time-consecutive samples.
In another aspect of the present invention the expressing step comprises expressing each of the constraints as (anxe2x88x92bn)xe2x89xa6cxe2x89xa6(an+1xe2x88x92bn).
In another aspect of the present invention there is provided a method for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements, the method including measuring the behavior of two elements of a system over time with respect to mutual interaction, thereby producing two behavior functions, expressing a plurality of constraints for a plurality of theoretical distances ci between the behavior functions, and determining that the elements are behaving as mutually interacting elements where there exists a plurality of actual distances ci that satisfies the constraints.
In another aspect of the present invention the expressing step comprises maintaining an upper bound and a lower bound on each of the plurality of theoretical distances ci, and the determining step comprises determining where the lower bound is smaller than or equal to the higher bound for any of the constraints.
In another aspect of the present invention the expressing step comprises expressing each of the constraints using a plurality of samples an of one of the functions taken at times at1, at2 . . . , atn, a first plurality of time-consecutive samples bn and a second plurality of time-consecutive samples btn of the other of the functions taken at times bt1, bt2 . . . , btn, where at1xe2x89xa6bt1xe2x89xa6at2xe2x89xa6bt2xe2x89xa6 . . . atnxe2x89xa6btn., and selecting each of the constraints from of a set of constraints defined by the pattern a1xe2x88x92b1xe2x89xa6c1xe2x89xa6a2xe2x88x92b1a2xe2x88x92b2xe2x89xa6c2xe2x89xa6min(a2xe2x88x92b1+P(bxe2x80x22xe2x88x92bxe2x80x21), a3xe2x88x92b2)a3xe2x88x92b3xe2x89xa6c3xe2x89xa6min(a2xe2x88x92b1+P(bxe2x80x23xe2x88x92bxe2x80x21), a3xe2x88x92b2+P(bxe2x80x23xe2x88x92bxe2x80x22), a4xe2x88x92b3).
In another aspect of the present invention there is provided apparatus for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements, the apparatus including means for measuring the behavior of two elements of a system over time with respect to mutual interaction, thereby producing two behavior functions, means for expressing a plurality of constraints on a theoretical distance c between the behavior functions, and means for determining that the elements are behaving as mutually interacting elements where there exists an actual distance c satisfies the constraints.
In another aspect of the present invention the expressing means comprises means for maintaining an upper bound and a lower bound on the theoretical distance c, and the determining means comprises means for determining where the lower bound is smaller than or equal to the higher bound for any of the constraints.
In another aspect of the present invention the expressing means comprises means for expressing each of the constraints using at least two time-consecutive samples (an, an+1) of one of the functions and at least one sample (bn) of the other of the functions that is time-intermediate the time-consecutive samples.
In another aspect of the present invention the expressing means comprises means for expressing each of the constraints as (anxe2x88x92bn)xe2x89xa6cxe2x89xa6(an+1xe2x88x92bn).
In another aspect of the present invention the expressing means comprises means for expressing each of the distances using at least two time-consecutive samples (an, an+1) of one of the functions and at least one sample (bn) of the other of the functions that is taken at the same time as one of the time-consecutive samples.
In another aspect of the present invention the expressing means comprises means for expressing each of the constraints as (anxe2x88x92bn)xe2x89xa6cxe2x89xa6(an+1xe2x88x92bn).
In another aspect of the present invention there is provided apparatus for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements, the apparatus including means for measuring the behavior of two elements of a system over time with respect to mutual interaction, thereby producing two behavior functions, means for expressing a plurality of constraints for a plurality of theoretical distances ci between the behavior functions, and means for determining that the elements are behaving as mutually interacting elements where there exists a plurality of actual distances ci that satisfies the constraints.
In another aspect of the present invention the expressing means comprises means for maintaining an upper bound and a lower bound on each of the plurality of theoretical distances ci, and where the determining means comprises means for determining where the lower bound is smaller than or equal to the higher bound for any of the constraints.
In another aspect of the present invention the expressing means comprises means for expressing each of the constraints using a plurality of samples an of one of the functions taken at times at1, at2 . . . , atn, a first plurality of time-consecutive samples bn and a second plurality of time-consecutive samples bxe2x80x2n of the other of the functions taken at times bt1, bt2 . . . , btn, where at1xe2x89xa6bt1xe2x89xa6at2xe2x89xa6bt2xe2x89xa6. . . atnxe2x89xa6btn., and means for selecting each of the constraints from of a set of constraints defined by the pattern a1xe2x88x92b1xe2x89xa6c1xe2x89xa6a2xe2x88x92b1a2xe2x88x92b2xe2x89xa6c2xe2x89xa6min(a2xe2x88x92b1+P(bxe2x80x22xe2x88x92bxe2x80x21), a3xe2x88x92b2)a3xe2x88x92b3xe2x89xa6c3xe2x89xa6min(bxe2x80x22), a4xe2x88x92b3).
The disclosures of all patents, patent applications, and other publications mentioned in this specification and of the patents, patent applications, and other publications cited therein are hereby incorporated by reference in their entirety.